package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/12 13:28
 */
public class MinimizeTheDifference {


    public static void main(String[] args) {
        MinimizeTheDifference test = new MinimizeTheDifference();

        // 0
//        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//        int target = 13;

        // 94
//        int[][] mat = {{1},{2},{3}};
//        int target = 100;

        // 1
//        int[][] mat = {{1, 2, 9, 8, 7}};
//        int target = 6;

        // 1
        int[][] mat ={{65},{45},{45},{69},{55},{60},{29},{25},{16},{5},{62},{16},{29},{19},{34},{2},{24},{32},{66},{62},{60},{46},{42},{37},{51},{4},{41},{4},{66},{20},{9},{4},{66},{6},{56},{10},{51},{44},{7},{8},{5},{44},{28},{7},{10},{7},{24},{62},{19},{14},{45},{68},{9},{14},{51},{28},{8},{57},{59},{6},{54},{8},{19},{16},{63},{45},{33},{15},{33},{67}};
        int target = 800;

        int i = test.minimizeTheDifference(mat, target);
        System.out.println(i);


    }


    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length;
        int[] as = new int[801];
        int a = Integer.MAX_VALUE;
        int[] bs = new int[801];
        int b = Integer.MAX_VALUE;
        int[] ints = mat[0];
        for (int anInt : ints) {
            as[anInt] = 1;
        }
        for (int i = 1; i < m; i++) {
            ints = mat[i];
            for (int anInt : ints) {
                b = Integer.MAX_VALUE;
                if (a != Integer.MAX_VALUE) {
                    b = a + anInt;
                }
                for (int j = 0; j <= 800; j++) {
                    if (as[j] == 1) {
                        if (j + anInt <= 800) {
                            bs[j + anInt] = 1;
                        } else {
                            b = Math.min(b, j + anInt);
                        }
                    }
                }
            }
            a = b;
            for (int j = 0; j <= 800; j++) {
                as[j] = bs[j];
                bs[j] = 0;
            }
        }
        int min = a - target;
        for (int i = 0; i <= 800; i++) {
            if (as[i] == 1) {
                min = Math.min(min, Math.abs(i - target));
            }
        }
        return min;
    }

}
